package tree

//计算给定二叉树的所有左叶子之和

//深度优先搜索
//时间复杂度：O(n)，其中 n 是树中的节点个数。
//空间复杂度：O(n),空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下，树呈现链式结构，深度为 O(n)，对应的空间复杂度也为 O(n)。
func SumOfLeftLeavesDFS(root *Node) int {

	if root == nil {
		return 0
	}

	var dfs func(root *Node) int
	dfs = func(node *Node) (ans int) {
		//如果是左子树不为空
		if node.Left != nil {
			//如果为叶子节点，则累加结果
			if isLeafNode(node.Left) {
				ans += node.Left.Val
			} else {
				//递归左子树
				ans += dfs(node.Left)
			}
		}

		//如果右子树不为空且右子树也不是叶子节点，递归右子树寻找左叶子节点
		if node.Right != nil && !isLeafNode(node.Right) {
			ans += dfs(node.Right)
		}
		return
	}
	return dfs(root)
}

func SumOfLeafLeavesBFS(root *Node) (ans int) {
	if root == nil {
		return 0
	}

	queue := make([]*Node, 0)
	queue = append(queue, root)
	//q := []*Node{root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		//判断左右子树情况
		if node.Left != nil {
			if isLeafNode(node.Left) {
				ans += node.Left.Val
			} else {
				queue = append(queue, node.Left)
			}
		}

		if node.Right != nil && !isLeafNode(node.Right) {
			queue = append(queue, node.Right)
		}
	}

	return
}
func isLeafNode(node *Node) bool {
	return node.Left == nil && node.Right == nil
}
